package fun.ticsmyc.dataStructure;

import fun.ticsmyc.tools.BinaryTreeTools;
import fun.ticsmyc.tools.TreeNode;
import org.junit.Test;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

/**
 * 递归and非递归  先序中序后序
 * @author Ticsmyc
 * @package fun.ticsmyc.dataStructure
 * @date 2020-02-16 18:18
 */

public class 二叉树的遍历 {



    /**
     * 递归先序
     * @param root
     */
    public static void preOrderRecur(TreeNode root){
        if(root == null){
            return;
        }
        System.out.print(root.val +" ");
        preOrderRecur(root.left);
        preOrderRecur(root.right);
    }

    /**
     * 递归中序
     * @param root
     */
    public static void inOrderRecur(TreeNode root){
        if(root == null){
            return;
        }
        inOrderRecur(root.left);
        System.out.print(root.val +" ");
        inOrderRecur(root.right);
    }

    /**
     * 递归后序
     * @param root
     */
    public static void posOrderRecur(TreeNode root){
        if(root == null){
            return;
        }
        posOrderRecur(root.left);
        posOrderRecur(root.right);
        System.out.print(root.val +" ");
    }

    /**
     * 非递归先序
     * @param root
     */
    public static void preOrderUnRecur(TreeNode root){
        if(root == null){
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.empty()){
            TreeNode TreeNode = stack.pop();
            System.out.print(TreeNode.val +" ");
            if(TreeNode.right!=null){
                stack.push(TreeNode.right);
            }
            if(TreeNode.left!=null){
                stack.push(TreeNode.left);
            }
        }
    }

    /**
     * 非递归中序
     * @param root
     */
    public static void inOrderUnRecur(TreeNode root){
        if(root == null){
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        while(root != null || !stack.empty()){
            if(root!=null){
                stack.push(root);
                root=root.left;
            }else{
                root = stack.pop();
                System.out.print(root.val +" ");
                root =root.right;
            }
        }
    }

    /**
     * 非递归后序（两个栈）
     * @param root
     */
    public static void posOrderUnRecur(TreeNode root){
        if(root == null){
            return;
        }
        //先序： 中左右  -> 中右左
        //中右左逆序 -> 左右中
        Stack<TreeNode> stack = new Stack<>();
        Stack<TreeNode> posStack =new Stack<>();
        stack.push(root);
        while(!stack.empty()){
            root = stack.pop();
            posStack.push(root);
            //temp
            if(root.left!=null){
                stack.push(root.left);
            }
            if(root.right!=null){
                stack.push(root.right);
            }
        }
        while(!posStack.empty()){
            System.out.print(posStack.pop().val +" ");
        }
    }

    /**
     * 层序
     * @param root
     */
    public static void levelOrder(TreeNode root){
        if(root ==null){
            return;
        }
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur =queue.poll();
            System.out.print(cur.val +" ");
            if(cur.left != null){
                queue.offer(cur.left);
            }
            if(cur.right!= null){
                queue.offer(cur.right);
            }
        }
    }

    /**
     * 非递归后序（一个栈）
     * @param root
     */
    public static void posOrderUnRecur2(TreeNode root){
        if(root == null){
            return;
        }
        TreeNode lastPop = null;
        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode stackPeek = stack.peek();
            if(stackPeek.left!= null &&stackPeek.left!=lastPop &&
                    (lastPop == null||stackPeek.right !=lastPop)){
                stack.push(stackPeek.left);

            } else if (stackPeek.right != null && (lastPop == null || lastPop != stackPeek.right)) {
                stack.push(stackPeek.right);
            }else {
                lastPop = stack.pop();
                System.out.print(lastPop.val + " ");
            }
        }
    }
    @Test
    public void test() {
        TreeNode head = new TreeNode(5);
        head.left = new TreeNode(3);
        head.right = new TreeNode(8);
        head.left.left = new TreeNode(2);
        head.left.right = new TreeNode(4);
        head.left.left.left = new TreeNode(1);
        head.right.left = new TreeNode(7);
        head.right.left.left = new TreeNode(6);
        head.right.right = new TreeNode(10);
        head.right.right.left = new TreeNode(9);
        head.right.right.right = new TreeNode(11);

        BinaryTreeTools.printTree(head);
        // recursive
        System.out.println("==============recursive==============");
        System.out.print("pre-order: ");
        preOrderRecur(head);
        System.out.println();
        System.out.print("in-order: ");
        inOrderRecur(head);
        System.out.println();
        System.out.print("pos-order: ");
        posOrderRecur(head);
        System.out.println();

        // unrecursive
        System.out.println("============unrecursive=============");
        System.out.print("pre-order: ");
        preOrderUnRecur(head);
        System.out.println();
        System.out.print("in-order: ");
        inOrderUnRecur(head);
        System.out.println();
        System.out.print("pos-order: ");
        posOrderUnRecur2(head);
        System.out.println();

        //层序
        System.out.println("============level=============");
        levelOrder(head);
        System.out.println();
    }
}


